home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / modelers / geomview / source.lha / Geomview / src / bin / geomutil / plutil / polymerge.c < prev   
Encoding:
C/C++ Source or Header  |  1993-07-28  |  17.0 KB  |  788 lines
  1. /*
  2.  * Squeeze OFF files.
  3.  * Merges collinear edges and coplanar faces.
  4.  */
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <math.h>
  8. #include <stdlib.h>    /* for qsort(), malloc() */
  9.  
  10. extern char *strdup(const char *);
  11.  
  12. #define    VSUB(a, b, dst)  (dst)->x = (a)->x - (b)->x, \
  13.              (dst)->y = (a)->y - (b)->y, \
  14.              (dst)->z = (a)->z - (b)->z
  15.  
  16. #define    VDOT(a, b)     (a)->x*(b)->x + (a)->y*(b)->y + (a)->z*(b)->z
  17.  
  18. #define VCROSS(a, b, dst) (dst)->x = (a)->y * (b)->z - (a)->z * (b)->y, \
  19.               (dst)->y = (a)->z * (b)->x - (a)->x * (b)->z, \
  20.               (dst)->z = (a)->x * (b)->y - (a)->y * (b)->x
  21.  
  22. float    EPS_LINEAR=    0.0001;    /* Max unit-vector cross product for collinearity */
  23. float    EPS_NORMAL=    0.0009;    /* Max sin^2 theta between normals for coplanarity */
  24. float    EPS_POINT=    0.00001;/* Max distance between coincident vertices */
  25.  
  26. #define    F_VERT    0x1
  27. #define    F_EDGE    0x2
  28. #define    F_FACE    0x4
  29. #define    F_EVOLVER 0x8
  30.  
  31. typedef struct vertex V;
  32. typedef struct face   F;
  33. typedef struct faceedge Fe;
  34. typedef struct edge   E;
  35.  
  36. typedef struct point {
  37.     float x, y, z, w;
  38. } P;
  39.  
  40.  
  41. struct vertex {
  42.     P p;
  43.     int ref;
  44.     int index;
  45.     float *more;
  46. };
  47.  
  48. struct faceedge {
  49.     F *face;
  50.     Fe *prev, *next;    /* double links in face-edges of this face */
  51.     E  *edge;
  52.     int sign;        /* direction w.r.t. edge */
  53.     P n;            /* adopted surface normal at this edge */
  54.     Fe *elink;
  55. };
  56.  
  57. struct face {
  58.     Fe *fedges;
  59.     char *affix;
  60. };
  61.  
  62. struct edge {
  63.     V *v[2];        /* vertex pointers */
  64.     E *link;        /* hash table link */
  65.     P to;            /* normalized edge direction vector */
  66.     Fe *feds;        /* faceedge's on this edge */
  67.     int index;        /* for numbering edges for .fe format */
  68. };
  69.  
  70.  
  71. int nv, nf, tossedf, nhash;
  72. V *Vs;                /* All vertices */
  73. F *Fs;                /* All faces */
  74. E **ehash;            /* Array of hash-table head pointers */
  75. int nhash;
  76. int flags = F_VERT|F_EDGE|F_FACE;
  77. int debug = 0;
  78. int vdim = 3;
  79.  
  80. Fe *fedge( F *f, V *v0, V *v1 );
  81.  
  82. #define    New(t)        (t *) malloc(sizeof(t))
  83. #define NewN(t, N)    (t *) malloc((N)*sizeof(t))
  84.  
  85. main(argc, argv)
  86.     char *argv[];
  87. {
  88.     register int i;
  89.     int tnv, tne, any;
  90.     int binary = 0, vertsize = 0;
  91.     char *C = "", *N = "", *four = "";
  92.     extern int optind;
  93.     extern char *optarg;
  94.  
  95.     while((i = getopt(argc, argv, "bdv:e:f:VEF")) != EOF) {
  96.     switch(i) {
  97.     case 'b': flags |= F_EVOLVER; break;
  98.     case 'd': debug = 1; break;
  99.     case 'v': EPS_POINT = atof(optarg); break;
  100.     case 'e': EPS_LINEAR = atof(optarg); EPS_LINEAR *= EPS_LINEAR; break;
  101.     case 'f': EPS_NORMAL = atof(optarg); EPS_NORMAL *= EPS_NORMAL; break;
  102.     case 'V': flags &= ~F_VERT; break;
  103.     case 'E': flags &= ~F_EDGE; break;
  104.     case 'F': flags &= ~F_FACE; break;
  105.     default:
  106.         fprintf(stderr, "\
  107. Usage: polymerge [-v vertex_thresh] [-e edge_thresh] [-f face_thresh]\n\
  108.     [-V][-E][-F][-d][-b] [infile.off]\n\
  109. Merges coincident vertices, collinear edges, coplanar faces of an OFF object.\n\
  110. -v vertex_thresh: max separation for \"coincident\" vertices (default %g)\n\
  111. -e edge_thresh    : max sin(theta) for \"collinear\" edges (default %g)\n\
  112. -f face_thresh    : max sin(theta) for \"coplanar\" facet normals (default %.4g)\n\
  113. -V  -E  -F    : don't try to merge vertices/edges/faces\n\
  114. -b         : create output in evolver .fe format\n\
  115. -d         : debug\n",
  116.     EPS_POINT, sqrt(EPS_LINEAR), sqrt(EPS_NORMAL));
  117.         exit(1);
  118.     }
  119.     }
  120.     if(optind < argc) {
  121.     if(freopen(argv[argc-1], "r", stdin) == NULL) {
  122.         fprintf(stderr, "polymerge: can't open input: ");
  123.         perror(argv[argc-1]);
  124.         exit(1);
  125.     }
  126.     }
  127.  
  128.     vdim = 3;
  129.     for(;;) {
  130.     switch( fnextc(stdin, 0) ) {
  131.     case 'N': N = "N"; vertsize += 3; goto swallow;
  132.     case 'C': C = "C"; vertsize += 4; goto swallow;
  133.     case '4':
  134.         four = "4";
  135.         vdim = 4;
  136.         flags &= ~(F_EDGE|F_FACE);
  137.         goto swallow;
  138.       swallow:
  139.     case '{': case '=': fgetc(stdin); break;
  140.     case 'a':    /* Appearance?  Silently swallow keyword */
  141.         fexpectstr(stdin, "appearance");
  142.         if(fnextc(stdin, 0) == '{') {
  143.         int c, brack = 0;
  144.         do {
  145.             if((c = fgetc(stdin)) == '{') brack++;
  146.             else if(c == '}') brack--;
  147.         } while(brack > 0 && c != EOF);
  148.         }
  149.         break;
  150.         
  151.     default: goto done;
  152.     }
  153.     }
  154.   done:
  155.     fexpecttoken(stdin, "OFF");    /* swallow optional OFF prefix */
  156.     if(fexpecttoken(stdin, "BINARY") == 0) {
  157.     binary = 1;
  158.     fnextc(stdin, 1);
  159.     fgetc(stdin);
  160.     }
  161.  
  162.     if(fgetni(stdin, 1, &nv, 0) <= 0 ||
  163.     fgetni(stdin, 1, &nf, 0) <= 0 ||
  164.     fgetni(stdin, 1, &nhash, 0) <= 0 || nv <= 0 || nf <= 0) {
  165.        fprintf(stderr, "polymerge: Input not an OFF file.\n");
  166.        exit(1);
  167.     }
  168.  
  169.     nhash = (nf + nv + 4) / 2;
  170.     if(nhash < 16) nhash = 17;
  171.     if(!(nhash & 1)) nhash++;
  172.     ehash = NewN(E *, nhash);
  173.     bzero((char *)ehash, nhash*sizeof(E *));
  174.  
  175.     Vs = NewN(V, nv);
  176.     Fs = NewN(F, nf);
  177.  
  178.     for(i = 0; i < nv; i++) {
  179.     V *vp = &Vs[i];
  180.     
  181.     vp->p.w = 1;
  182.     if(fgetnf(stdin, vdim, &vp->p, binary) < vdim) {
  183.       badvert:
  184.         fprintf(stderr, "polymerge: error reading vertex %d/%d\n", i,nv);
  185.         exit(1);
  186.     }
  187.     if(vertsize) {
  188.         Vs[i].more = NewN(float, vertsize);
  189.         if(fgetnf(stdin, vertsize, Vs[i].more, binary) < vertsize)
  190.         goto badvert;
  191.     }
  192.     Vs[i].ref = 0;
  193.     Vs[i].index = i;
  194.     }
  195.  
  196.     /*
  197.      * Combine vertices
  198.      */
  199.     if(flags & F_VERT)
  200.     vmerge();
  201.  
  202.     /*
  203.      * Load faces
  204.      * The fedge() calls here assume we've already merged all appropriate
  205.      * vertices.
  206.      */
  207.  
  208.     tossedf = 0;
  209.     for(i = 0; i < nf; i++) {
  210.     register F *fp = &Fs[i];
  211.     register Fe *fe;
  212.     int nfv, k, c;
  213.     int v, ov, v0;
  214.     Fe head;
  215.     char *cp;
  216.     char aff[512];
  217.  
  218.     if(fgetni(stdin, 1, &nfv, binary) <= 0 || nfv <= 0) {
  219.         fprintf(stderr, "polymerge: error reading face %d/%d\n",
  220.         i, nf);
  221.         exit(1);
  222.     }
  223.     head.prev = head.next = &head;
  224.     fp->fedges = &head;
  225.     fgetni(stdin, 1, &v, binary);
  226.     if(v < 0 || v >= nv) {
  227.         fprintf(stderr, "polymerge: bad vertex %d on face %d\n", v, i);
  228.         exit(1);
  229.     }
  230.     v0 = ov = Vs[v].index;        /* Use common vertex if merged */
  231.     for(k = 1; k < nfv; k++, ov = v) {
  232.         fgetni(stdin, 1, &v, binary);
  233.         if(v < 0 || v >= nv) {
  234.         fprintf(stderr, "polymerge: bad vertex %d on face %d\n", v, i);
  235.         exit(1);
  236.         }
  237.         v = Vs[v].index;        /* Use common vertex if merged */
  238.         if(ov == v)
  239.         continue;
  240.         head.prev->next = fe = fedge(fp, &Vs[ov], &Vs[v]);
  241.         fe->prev = head.prev;
  242.         fe->next = &head;
  243.         head.prev = fe;
  244.     }
  245.     if(v != v0) {
  246.         fe = fedge(fp, &Vs[v], &Vs[v0]);
  247.         head.prev->next = fe;
  248.         fe->prev = head.prev;
  249.         fe->next = &head;
  250.         head.prev = fe;
  251.     }
  252.     head.next->prev = head.prev;
  253.     if(head.next == &head) {
  254.         /*
  255.          * Degenerate face here
  256.          */
  257.         fp->fedges = NULL;
  258.         tossedf++;
  259.         debug && printf("# Face %d degenerate already\n", i);
  260.     } else {
  261.         head.prev->next = fp->fedges = head.next;
  262.     }
  263.  
  264.     if(binary) {
  265.         int nfc;
  266.         float c;
  267.         fgetni(stdin, 1, &nfc, binary);
  268.         if(nfc > 4) {
  269.         fprintf(stderr, "Bad face color count 0x%x", nfc);
  270.         exit(1);
  271.         }
  272.         for(cp = aff; --nfc >= 0; cp += strlen(cp)) {
  273.         fgetnf(stdin, 1, &c, binary);
  274.         sprintf(cp, " %g", c);
  275.         }
  276.     } else {
  277.         (void) fnextc(stdin, 1);
  278.         for(cp = aff; (c = getc(stdin)) != EOF && c != '\n' && cp < &aff[511]; )
  279.         *cp++ = c;
  280.     }
  281.     *cp = '\0';
  282.     fp->affix = (cp > aff) ? strdup(aff) : "";
  283.     }
  284.  
  285.     /*
  286.      * Compute face normals -- actually corner normals, since we avoid
  287.      * assuming faces are planar.  As a side effect, we detect & join
  288.      * collinear edges.
  289.      */
  290.     if(flags & F_EDGE) {
  291.     for(i = 0; i < nf; i++) {
  292.         normalize(&Fs[i]);
  293.     }
  294.     }
  295.  
  296.     /*
  297.      * Locate edges bounding faces with the same normal direction.
  298.      */
  299.     if(flags & F_FACE) {
  300.       do {
  301.     any = 0;
  302.  
  303.     for(i = 0; i < nhash; i++) {
  304.         E *e;
  305.  
  306.         for(e = ehash[i]; e != NULL; e = e->link) {
  307.         register Fe *fe, *fee;
  308.  
  309.         for(fe = e->feds; fe != NULL; fe = fe->elink) {
  310.             for(fee = fe->elink; fee != NULL; fee = fee->elink) {
  311.             register float dn;
  312.  
  313.             dn = VDOT(&fe->n, &fee->n);
  314.             if(fabs(1 - dn*dn) < EPS_NORMAL) {
  315.                 /*
  316.                  * OK, merge fee into fe
  317.                  */
  318.                 femerge(fe, fee);
  319.                 any++;
  320.                 goto another;
  321.             }
  322.             }
  323.         }
  324.           another: ;
  325.         }
  326.     }
  327.     debug && printf("# %d faces merged this pass.\n", any);
  328.       } while(any);
  329.     }
  330.  
  331.     /*
  332.      * Scan for unused edges.
  333.      */
  334.     for(i = 0; i < nv; i++)
  335.     Vs[i].ref = 0;
  336.     tne = 0;
  337.     for(i = 0; i < nhash; i++) {
  338.     E *e;
  339.     for(e = ehash[i]; e != NULL; e = e->link) {
  340.         if(e->feds != NULL) {
  341.         e->v[0]->ref++;
  342.         e->v[1]->ref++;
  343.         e->index = ++tne;
  344.         }
  345.     }
  346.     }
  347.     /*
  348.      * Renumber used vertices.
  349.      */
  350.     if(flags & 1) {
  351.     tnv = 0;
  352.     for(i = 0; i < nv; i++)
  353.         Vs[i].index = Vs[i].ref ? tnv++ : -i-1;
  354.     } else {
  355.     tnv = nv;
  356.     }
  357.  
  358. if (flags & F_EVOLVER) /* Produce Brakke's evolver .fe format */
  359. {
  360.     int j=0;
  361.     if (vdim == 4) printf("space_dimension 4\n");
  362.     printf("vertices\n");
  363.     for(i = 0; i < nv; i++) {
  364.     register V *v = &Vs[i];
  365.     int k;
  366.     if(v->ref || !(flags & 1)) {
  367.         v->index = ++j;
  368.         printf("%d\t%g %g %g", v->index, v->p.x, v->p.y, v->p.z);
  369.         if(vdim == 4) printf(" %g", v->p.w);
  370.         if(vertsize) {
  371.         printf("  ");
  372.         for(k = 0; k < vertsize; k++)
  373.             printf(" %g", v->more[k]);
  374.         }
  375.         printf("\n");
  376.     }
  377.     }
  378.     printf("\nedges\n");
  379.     for(i = 0; i < nhash; i++) {
  380.     E *e;
  381.     for(e = ehash[i]; e != NULL; e = e->link)
  382.         if(e->feds != NULL)
  383.         printf("%d\t%d %d\n", e->index,e->v[0]->index,e->v[1]->index);
  384.     }
  385.  
  386.     printf("\nfaces\n");
  387.     j=0;
  388.     for(i=0; i<nf; i++) {
  389.     register Fe *fe, *fee;
  390.     int k, nfv;
  391.  
  392.     fe = Fs[i].fedges;
  393.     if(fe == NULL)
  394.         continue;
  395.     for(fee = fe, k = 1; (fee = fee->next) != fe; k++)
  396.         ;
  397.     if ((nfv = k)<3)
  398.         continue;    /* don't print faces of less than 3 sides */
  399.     printf("%d", ++j);
  400.     for(fee = fe, k = nfv; --k >= 0; fee = fee->next)
  401.         printf(" %d", (1-2*fee->sign)*fee->edge->index);
  402.     printf("\n");
  403.     }
  404. }
  405. else    /* Produce OFF format */
  406. {
  407.     printf("%s%s%sOFF\n%d %d %d\n", C, N, four, tnv, nf - tossedf, tne);
  408.     for(i = 0; i < nv; i++) {
  409.     register V *v = &Vs[i];
  410.     int k;
  411.     if(v->ref || !(flags & F_VERT)) {
  412.         printf("%g %g %g", v->p.x, v->p.y, v->p.z);
  413.         if(vdim == 4) printf(" %g", v->p.w);
  414.         if(vertsize) {
  415.         printf("  ");
  416.         for(k = 0; k < vertsize; k++)
  417.             printf(" %g", v->more[k]);
  418.         }
  419.         if(debug)
  420.         printf("\t# %d [%d] #%d", v->index, v->ref, i);
  421.         printf("\n");
  422.     }
  423.     }
  424.     printf("\n");
  425.     /* ho hum */
  426.     for(i=0; i<nf; i++) {
  427.     register Fe *fe, *fee;
  428.     int k, nfv;
  429.  
  430.     fe = Fs[i].fedges;
  431.     if(fe == NULL)
  432.         continue;
  433.     for(fee = fe, k = 1; (fee = fee->next) != fe; k++)
  434.         ;
  435.     nfv = k;
  436.     printf("%d", nfv);
  437.     for(fee = fe, k = nfv; --k >= 0; fee = fee->next)
  438.         printf(" %d", fee->edge->v[fee->sign]->index);
  439.     printf("\t%s", Fs[i].affix);
  440.     if(debug) {
  441.         printf(" #");
  442.         for(fee = fe, k = nfv; --k >= 0; fee = fee->next)
  443.         printf(" %d", fee->edge->v[fee->sign] - Vs);
  444.     }
  445.     printf("\n");
  446.     }
  447. }
  448.     exit(1);
  449. }
  450.  
  451. /*
  452.  * Add a new faceedge
  453.  */
  454. Fe *
  455. fedge(F *f, V *v0, V *v1)
  456. {
  457.     Fe *fe;
  458.     E *e;
  459.     int t;
  460.     int i0, i1;
  461.     float r;
  462.  
  463.     fe = New(Fe);
  464.     fe->face = f;
  465.     fe->sign = 0;
  466.     i0 = v0->index;
  467.     i1 = v1->index;
  468.     if(i0 > i1) {
  469.     V *tv = v0;
  470.     v0 = v1;
  471.     v1 = tv;
  472.     i0 = v0->index;
  473.     i1 = v1->index;
  474.     fe->sign = 1;
  475.     }
  476.  
  477.     t = (unsigned long)(v0->index + v1->index + v0->index*v1->index) % nhash;
  478.                     /* Symmetric hash function */
  479.     for(e = ehash[t]; e != NULL; e = e->link)
  480.     if(e->v[0]->index == i0 && e->v[1]->index == i1)
  481.         goto gotit;
  482.  
  483.     e = New(E);
  484.     e->v[0] = v0;
  485.     e->v[1] = v1;
  486.     e->feds = NULL;
  487.     VSUB(&v0->p, &v1->p, &e->to);
  488.     r = VDOT(&e->to, &e->to);
  489.     if(r != 0) {
  490.     r = 1/sqrt(r);
  491.     e->to.x *= r;  e->to.y *= r;  e->to.z *= r;
  492.     } else 
  493.     debug && printf("# Coincident: %d == %d [%g %g %g]\n", v0->index, v1->index, v0->p.x,v0->p.y,v0->p.z);
  494.     e->link = ehash[t];
  495.     ehash[t] = e;
  496.  gotit:
  497.     fe->edge = e;
  498.     fe->elink = e->feds;
  499.     e->feds = fe;
  500.     return fe;
  501. }
  502.  
  503. /*
  504.  * Remove a faceedge from its edge list
  505.  */
  506. unfedge(fe)
  507.     register Fe *fe;
  508. {
  509.     register Fe **fepp;
  510.     
  511.     for(fepp = &fe->edge->feds; *fepp != NULL; fepp = &(*fepp)->elink) {
  512.     if(*fepp == fe) {
  513.         *fepp = fe->elink;
  514.         break;
  515.     }
  516.     }
  517.     free(fe);
  518. }
  519.  
  520. /*
  521.  * Merge two faces
  522.  * We delete these face-edges from both faces
  523.  */
  524. femerge(fe1, fe2)
  525.     register Fe *fe1, *fe2;
  526. {
  527.     F *f1, *f2;
  528.     register Fe *tfe;
  529.  
  530.     if(fe1->face == fe2->face) {
  531.     debug && printf("# Merging two edges of face %d -- tossing it.\n",
  532.         fe1->face - Fs);
  533.     deface(fe1->face);
  534.     return;
  535.     }
  536.  
  537.     if(fe1->sign == fe2->sign) {
  538.     /*
  539.      * Messy.  To merge these, we need to reverse all the links
  540.      * in one of the two faces.
  541.      */
  542.     Fe *xfe;
  543.     tfe = fe2;
  544.     do {
  545.         tfe->sign ^= 1;
  546.         xfe = tfe->next;
  547.         tfe->next = tfe->prev;
  548.         tfe->prev = xfe;
  549.         tfe = xfe;
  550.     } while(tfe != fe2);
  551.     }
  552.     fe1->prev->next = fe2->next;
  553.     fe2->next->prev = fe1->prev;
  554.     fe1->next->prev = fe2->prev;
  555.     fe2->prev->next = fe1->next;
  556.  
  557.     f1 = fe1->face;
  558.     f2 = fe2->face;
  559.     if(f1->fedges == fe1)
  560.     f1->fedges = fe2->next;
  561.     if(debug)
  562.         printf("# Merged face %d into %d (vertices %d %d) n1.n2 %g\n",
  563.         f2-Fs, f1-Fs,
  564.         fe1->edge->v[fe1->sign]->index,
  565.         fe1->edge->v[1 - fe1->sign]->index,
  566.         VDOT(&fe1->n, &fe2->n));
  567.     tfe = fe2->next;
  568.     if(tfe == NULL) {
  569.     fprintf(stderr, "polymerge: face f2 already deleted?\n");
  570.     } else {
  571.     do {
  572.         tfe->face = f1;
  573.     } while((tfe = tfe->next) != fe1->next);
  574.     }
  575.     f2->fedges = NULL;
  576.     tossedf++;
  577.     unfedge(fe1);
  578.     unfedge(fe2);
  579.  
  580.     /*
  581.      * Join collinear edges, recompute normals (might have changed a bit).
  582.      */
  583.     normalize(f1);
  584. }
  585.  
  586. #define PRETTY(x)  ((int)(x) - 0x10000000)
  587.  
  588. fecheck(fe)
  589.     Fe *fe;
  590. {
  591.     register Fe *fee;
  592.     int ne;
  593.     int onface = 0;
  594.     register F *f;
  595.     register E *e;
  596.  
  597.     if(fe == NULL)
  598.     return;
  599.     f = fe->face;
  600.     fprintf(stderr,"0x%x: on face %d (%x); ", fe, f - Fs, f);
  601.     fee = fe;
  602.     do {
  603.     fprintf(stderr," %s%x[%d%s%d] ", (f->fedges == fee) ? "*" : "",
  604.         PRETTY(fee),
  605.         fee->edge->v[0]->index,
  606.         fee->sign ? "<-" : "->",
  607.         fee->edge->v[1]->index);
  608.  
  609.     if(fee->face != f)
  610.         fprintf(stderr," Fe %x: face %d (%x) != %x\n",
  611.         PRETTY(fee), fee->face - Fs, fee->face, f);
  612.     if(fee->next->prev != fee)
  613.         fprintf(stderr," Fe %x: next %x next->prev %x\n",
  614.         PRETTY(fee), PRETTY(fee->next), PRETTY(fee->next->prev));
  615.     e = fee->edge;
  616.     fee = fee->next;
  617.     } while(fee != fe);
  618.     fprintf(stderr, "\n");
  619. }
  620.  
  621. E *
  622. echeck(v0, v1)
  623.     register int v0, v1;
  624. {
  625.     register E *e;
  626.  
  627.     int t = (v0 + v1 + v0*v1) % nhash;
  628.                     /* Symmetric hash function */
  629.     if(v0 > v1) v0 ^= v1, v1 ^= v0, v0 ^= v1;
  630.     for(e = ehash[t]; e != NULL; e = e->link) {
  631.     if(e->v[0] == &Vs[v0] && e->v[1] == &Vs[v1]) {
  632.         register Fe *fe;
  633.         fprintf(stderr, "E 0x%x %d-%d (%d-%d)  %x...\n",
  634.         e, v0,v1, e->v[0]->index, e->v[1]->index, PRETTY(e->feds));
  635.         for(fe = e->feds; fe != NULL; fe = fe->elink) {
  636.         fecheck(fe);
  637.         }
  638.     }
  639.     }
  640.     
  641.     return e;
  642. }
  643.  
  644.  
  645.  
  646. normalize(f)
  647.    F *f;
  648. {
  649.     register Fe *fe;
  650.  
  651.     fe = f->fedges;
  652.     if(fe == NULL)
  653.     return;
  654.     if(fe->prev == fe->next) {
  655.     debug && printf("# Face %d already degenerate -- tossing it.\n", f - Fs);
  656.     deface(f);
  657.     return;
  658.     }
  659.  
  660.     do {        /* loop over edges on this face */
  661.     P n;
  662.     float r;
  663.  
  664.     for(;;) {
  665.         register Fe *fn, *fee;
  666.         register P *pp, *qp;
  667.  
  668.         pp = &fe->edge->to;
  669.         fee = fe->next;
  670.         qp = &fee->edge->to;
  671.         VCROSS(pp, qp, &n);
  672.         r = VDOT(&n, &n);
  673.         if(r > EPS_LINEAR)
  674.         break;
  675.         /*
  676.          * Join collinear edges; produce a new edge
  677.          */
  678.         fn = fedge(f, fe->edge->v[fe->sign], fee->edge->v[1-fee->sign]);
  679.         fee->next->prev = fe->prev->next = fn;
  680.         fn->next = fee->next;
  681.         fn->prev = fe->prev;
  682.         if(fe == f->fedges || fee == f->fedges)
  683.         f->fedges = fn;    /* preserve headiness */
  684.         unfedge(fee);
  685.         if(fee != fe)
  686.         unfedge(fe);
  687.         if(fn->prev == fn->next) {
  688.         /*
  689.          * This face became degenerate -- toss it.
  690.          */
  691.         debug && printf("# degenerate face %d\n", f - Fs);
  692.         deface(f);
  693.         return;
  694.         }
  695.         fe = fn;
  696.     }
  697.  
  698.     r = 1/sqrt(r);
  699.     if(n.x < 0 ||  (n.x == 0 && n.y < 0 || (n.y == 0 && n.z < 0)))
  700.         r = -r;        /* Canonicalize */
  701.     fe->n.x = n.x*r;  fe->n.y = n.y*r;  fe->n.z = n.z*r;
  702.     } while((fe = fe->next) != f->fedges);
  703. }
  704.  
  705. /*
  706.  * Delete a face, erasing all edges.
  707.  */
  708. deface(f)
  709.     F *f;
  710. {
  711.     register Fe *fe, *fee;
  712.  
  713.     fe = f->fedges;
  714.     if(fe == NULL)
  715.     return;
  716.  
  717.     do {
  718.     fee = fe->next;
  719.     unfedge(fe);
  720.     fe = fee;
  721.     } while(fe != f->fedges);
  722.     f->fedges = NULL;
  723.     tossedf++;
  724. }
  725.  
  726. vcmp(p, q)
  727.     V **p, **q;
  728. {
  729.     register V *vp, *vq;
  730.     register float d;
  731.  
  732.     vp = *p;
  733.     vq = *q;
  734.     d = vp->p.x - vq->p.x;
  735.     if(d < 0) return -1;
  736.     if(d > 0) return 1;
  737.     d = vp->p.y - vq->p.y;
  738.     if(d < 0) return -1;
  739.     if(d > 0) return 1;
  740.     d = vp->p.z - vq->p.z;
  741.     if(d < 0) return -1;
  742.     if(d > 0) return 1;
  743.     if(vp->p.w == vq->p.w) return 0;
  744.     return(vp->p.w < vq->p.w ? -1 : 1);
  745. }
  746.  
  747. vmerge()
  748. {
  749.     V **vp;
  750.     int i, j;
  751.     register V *a, *b;
  752.     int nexti;
  753.  
  754.     vp = NewN(V *, nv);
  755.     for(i = 0, a = Vs; i < nv; i++) {
  756.     a->ref = 0;
  757.     vp[i] = a++;
  758.     }
  759.     qsort(vp, nv, sizeof(V *), vcmp);
  760.  
  761.     /*
  762.      * Now all matches will occur within X-runs
  763.      */
  764.     for(i = 0; i < nv; i = nexti ? nexti : i+1) {
  765.     nexti = 0;
  766.     a = vp[i];
  767.     if(a->ref)
  768.         continue;
  769.     for(j = i; ++j < nv; ) {
  770.         b = vp[j];
  771.         if(b->ref)
  772.         continue;
  773.         if(b->p.x - a->p.x > EPS_POINT)
  774.         break;
  775.  
  776.         if(fabs(a->p.y - b->p.y) < EPS_POINT
  777.             && fabs(a->p.z - b->p.z) < EPS_POINT
  778.             && (vdim == 3 || fabs(a->p.w - b->p.w) < EPS_POINT)) {
  779.         debug && printf("# Vtx %d->%d\n", b->index, a->index);
  780.         b->index = a->index;
  781.         b->ref++;
  782.         } else if(!nexti)
  783.         nexti = j;
  784.     }
  785.     }
  786.     free(vp);
  787. }
  788.